package com.againstsky.algorithm.sort;

import com.againstsky.algorithm.bean.SortBase;

/**
 * Created by agasinst on 2017/8/25.
 */
/*
* 希尔排序，适合处理大量的数据，比插入和选择排序快很多倍
*/
public class Shell extends SortBase {
    @Override
    public void sort(Comparable[] a) {
        int h=1;
        int N=a.length;
        while (h<N/3) h=3*h+1;
        while (h>=1){
            for (int i = 0; i < N; i++) {
                for (int j=i;j>=h&&less(a[j],a[j-h]);j-=h){
                    exch(a,j,j-h);
                }
            }
            h=h/3;
        }
    }
}
